public class SumOfTwoLists {

	// performs sum of two linked list in which every node is a digit
	
	/* Suppose you have 2 big numbers represented as linked lists, how do you add them and store the result in a separate linked list. eg
	 * 
	 */

	static class Node {
		int digit;
		Node next;

		public Node(int digit) {
			this.digit = digit;
		}
	}

	public static void main(String[] args) {
		
		StringBuilder sb = new StringBuilder();
		sb.append("robert");
		System.out.println(sb.reverse());

		// 15674
		Node node1 = new Node(9);
		Node node2 = new Node(5);
		node1.next = node2;
		Node node3 = new Node(6);
		node2.next = node3;
		Node node4 = new Node(7);
		node3.next = node4;
		Node node5 = new Node(4);
		node4.next = node5;

		// 767
		Node node6 = new Node(7);
		Node node7 = new Node(6);
		node6.next = node7;
		Node node8 = new Node(7);
		node7.next = node8;

		print(node1);
		System.out.println();
		print(node6);
		System.out.println();
		
		Node head = sum(node1, node2);
		print(head);
		System.out.println();
		
		print(node1);
		System.out.println();
	}

	private static Node sum(Node node1, Node node2) {

		if (node1 == null || node2 == null) {
			return node1 != null ? node1 : node2;
		}

		int length1 = getLength(node1);
		int length2 = getLength(node2);
		
		Node head = null;
		if (length1 > length2) {
			head = sumNodes(node1, length1, node2, length2);
		} else {
			head = sumNodes(node2, length2, node1, length1);
		}

		if (head.digit > 10) {
			Node newHead = new Node(head.digit / 10);
			head.digit %= 10;
			newHead.next = head;
			head = newHead;
		}

		return head;
	}

	private static Node sumNodes(Node node1, int length1, Node node2, int length2) {

		if (length1 - length2 > 0) {
			Node result = sumNodes(node1.next, length1 - 1, node2, length2);
			return addNodes(node1, new Node(0), result);
		} else {
			if (node1.next == null) {
				return addNodes(node1, node2, null);
			} else {
				Node result = sumNodes(node1.next, length1 - 1, node2.next,
						length2 - 1);
				return addNodes(node1, node2, result);
			}
		}
	}

	private static Node addNodes(Node node1, Node node2, Node lower) {

		Node node = new Node(0);
		int lowerPart = 0;
		if(lower != null) {
			lowerPart = lower.digit / 10;
			lower.digit = lower.digit % 10;
		}
		node.digit = node1.digit + node2.digit + lowerPart;
		node.next = lower;
		
		return node;
	}

	private static int getLength(Node node) {
		int length = 0;
		while (node != null) {
			length++;
			node = node.next;
		}
		return length;
	}

	private static void print(Node head) {
		if (head != null) {
			System.out.print(head.digit);
			print(head.next);
		}

	}
}
